import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class leetCodeResult_1 {

    @Test
    public void testGroupAnagrams(){
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        findMedianSortedArrays(nums1, nums2);
    }
    /**
     *
     代码
     测试用例
     测试结果
     测试结果
     49. 字母异位词分组
     中等
     相关标签
     相关企业
     给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

     字母异位词 是由重新排列源单词的所有字母得到的一个新单词。



     示例 1:

     输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
     示例 2:

     输入: strs = [""]
     输出: [[""]]
     示例 3:

     输入: strs = ["a"]
     输出: [["a"]]
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        LinkedList<List<String>> result = new LinkedList<List<String>>();
        //每个字母异位词的HashMap判断列表,Integer用于记录字母出现次数
        List<HashMap<Character, Integer>> wordsSet = new LinkedList<HashMap<Character, Integer>>();
        Integer emptyStrNum = 0;
        for (String each : strs) {
            //判断当前字母异位词的HashMap判断列表中是否包含此字母异位词
            boolean flag = true;
            Integer wordSetIndex = 0;
            HashMap<Character, Integer> distinctChar = new HashMap<Character, Integer>();
            for (int i = 0; i < each.length(); i++) {
                distinctChar.put(each.charAt(i), (distinctChar.containsKey(each.charAt(i)) ? distinctChar.get(each.charAt(i)) : 0) + 1);
            }
            if(distinctChar.isEmpty()){
                emptyStrNum++;
                continue;
            }
            for (; wordSetIndex < wordsSet.size(); wordSetIndex++) {
                HashMap<Character, Integer> eachWordSet = wordsSet.get(wordSetIndex);
                flag = true;
                for (int i = 0; i < each.length(); i++) {
                    if (!eachWordSet.containsKey(each.charAt(i)) || distinctChar.get(each.charAt(i)) != eachWordSet.get(each.charAt(i))) {
                        flag = false;
                    }
                }
                if (distinctChar.size() != eachWordSet.size()) {
                    flag = false;
                }
                if (flag) {
                    break;
                }
            }
            if(flag && !wordsSet.isEmpty()){
                result.get(wordSetIndex).add(each);
            }
            //如果当前单词不存在于字母异位词的HashMap判断列表中，将该单词新增在字母异位词的HashMap判断列表
            if(!flag || wordsSet.isEmpty()){
                HashMap<Character, Integer> newWordSet = new HashMap<Character, Integer>();
                for (int j = 0; j < each.length(); j++){
                    newWordSet.put(each.charAt(j), (newWordSet.containsKey(each.charAt(j)) ? newWordSet.get(each.charAt(j)) : 0) + 1);
                }
                wordsSet.add(newWordSet);
                LinkedList<String> strings = new LinkedList<String>();
                strings.add(each);
                result.add(strings);
            }
        }
        if (emptyStrNum > 0) {
            LinkedList<String> strings = new LinkedList<String>();
            for (int i = 0; i < emptyStrNum; i++) {
                strings.add("");
            }
            result.add(strings);
        }
        return result;
    }

    /**
     * 字母异位词试做一个单词的特征，将特征作为hashKey，同特征的单词作为hashvalue可以避免对字符特征关键词wordsSet的遍历而产生的O(N)时间复杂度(N代表同组字母异位词的组数)
     * 特征采用单词26个字符出现次数组成的字符串
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams_great(String[] strs) {
        HashMap<String, LinkedList<String>> resultMap = new HashMap<String, LinkedList<String>>();
        for (String each : strs) {
            int[] counts = new int[26];
            for (int i = 0; i < each.length(); i++) {
                counts[each.charAt(i) - 'a']++;
            }
            StringBuffer countBuffer = new StringBuffer();
            for (int i = 0; i < counts.length; i++) {
                countBuffer = countBuffer.append((char)('a' + i)).append(counts[i]);
            }
            if (resultMap.containsKey(countBuffer.toString())) {
                resultMap.get(countBuffer.toString()).add(each);
            }else{
                LinkedList<String> newstrs = new LinkedList<String>();
                newstrs.add(each);
                resultMap.put(countBuffer.toString(), newstrs);
            }
        }
        List<List<String>> result = new LinkedList<List<String>>();
        for (String each : resultMap.keySet()) {
            List<String> strings = resultMap.get(each);
            result.add(strings);
        }
        return result;
    }

    /**
     * 128. 最长连续序列
     * 尝试过
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     *
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     */
    public int longestConsecutive(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        HashMap<Integer, Integer> numMap = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
            numMap.put(num, 1);
        }
        int result = 0;
        for (; min <= max; min++) {
            int continueNum = 0;
            while(numMap.containsKey(min) && min <= max){
                continueNum = continueNum + 1;
                min++;
            }
            if (continueNum > result) {
                result = continueNum;
            }
        }
        return result;
    }

    public int longestConsecutive_better(int[] nums) {
        HashSet<Integer> integerSet = new HashSet<Integer>();
        for (int num : nums) {
            integerSet.add(num);
        }
        int result = 0;
        for (int num : integerSet) {
            if (!integerSet.contains(num - 1)) {    // <-这两行配合，避免了n^2的循环复杂度
                int continueNum = 1;
                int currentNum = num;
                while (integerSet.contains(currentNum + 1)) {  // <-这两行配合，避免了n^2的循环复杂度
                    num++;
                    continueNum++;
                }
                result = Math.max(result, continueNum);
            }
        }
        return result;
    }

    /**
     * 4. 寻找两个正序数组的中位数
     * 困难
     * 相关标签
     * 相关企业
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     *
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;
        LinkedList<Integer> objects = new LinkedList<Integer>();
        while(i < nums1.length || j < nums2.length){
            if (i < nums1.length && j < nums2.length && nums1[i] < nums2[j]) {
                objects.add(nums1[i]);
                i++;
            }else if(i < nums1.length && j < nums2.length && nums1[i] >= nums2[j]){
                objects.add(nums2[j]); 
                j++;
            }else if(i >= nums1.length && j < nums2.length){
                objects.add(nums2[j]);
                j++;
            }else if(j >= nums2.length && i < nums1.length){
                objects.add(nums1[i]);
                i++;
            }
        }
        if(objects.size() % 2 == 0){
            return (double) (objects.get((objects.size() / 2) - 1) + objects.get(objects.size() / 2)) / 2;
        }else{
            return (double) (objects.get((objects.size() - 1) / 2));
        }
    }

    /**
     * 74. 搜索二维矩阵
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个满足下述两条属性的 m x n 整数矩阵：
     *
     * 每行中的整数从左到右按非严格递增顺序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        return false;
    }

    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     *
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     */
    public void moveZeroes(int[] nums) {
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == 0) {
                int j = i;
                int k = j + 1;
                while (k < nums.length) {
                    nums[j] = nums[k];
                    j = k;
                    k = k + 1;
                }
                nums[j] = 0;
            }
        }
    }
}
